package october;

import java.util.*;

/*
Complete the below function which takes an arraylist and displays the list in the expected output 

Example input: 
List<Relation> input = newArrayList(); 

input.add(new Relation("animal", "mammal")); 
input.add(new Relation("animal", "bird")); 
input.add(new Relation("lifeform", "animal")); 
input.add(new Relation("cat", "lion")); 
input.add(new Relation("mammal", "cat")); 
input.add(new Relation("animal", "fish")); 

TreePrinter.printTree(input); 

Expected output: 
line 1: lifeform 
line 2: animal 
line 3: mammal 
line 4: cat 
line 5: lion 
line 6: bird 
line 7: fish
 */
public class ListAsTreePrinter {
    public static void main(String[] args) {
        List<Relation> input = new ArrayList();

        input.add(new Relation("animal", "mammal"));
        input.add(new Relation("animal", "bird"));
        input.add(new Relation("lifeform", "animal"));
        input.add(new Relation("cat", "lion"));
        input.add(new Relation("mammal", "cat"));
        input.add(new Relation("animal", "fish"));

        Relation.printTree(input);

    }

    private static class Relation {
        String parent;
        String child;

        public Relation(String parent, String child) {
            this.parent = parent;
            this.child = child;
        }

        public static void printTree(Iterable<Relation> rs) {
            Set<String> notRootNames = new HashSet<String>();
            Map<String, List<String>> relationsMap = new HashMap<String, List<String>>();
            for (Relation r : rs) {
                notRootNames.add(r.child);
                if (relationsMap.containsKey(r.parent)) relationsMap.get(r.parent).add(r.child);
                else {
                    List<String> newChildList = new LinkedList<String>();
                    newChildList.add(r.child);
                    relationsMap.put(r.parent, newChildList);
                }
            }
            for (String root : relationsMap.keySet()) {
                if (notRootNames.contains(root)) continue; // Not the root, was seen as a child in some relation
                printTree(root, relationsMap);
            }

        }

        private static void printTree(String root, Map<String, List<String>> relationsMap) {
            System.out.println(root);
            List<String> children = relationsMap.get(root);
            if (children != null) {
                for (String child : children) printTree(child, relationsMap);
            }
        }
    }
}
